package com.github.hgkmail.hello.leetcode101.firstsearch;

import java.util.*;

//回溯法
public class LC47Permutations2 {
    //因为数字可能重复，aCase不能用ArrayList，要使用Deque，从尾部操作
    public void backtrack(int[] nums, Map<Integer, Integer> counts, Deque<Integer> aCase, List<List<Integer>> res) {
        if (aCase.size()>=nums.length) {
            res.add(new ArrayList<>(aCase));
            return;
        }
        Set<Integer> keys = counts.keySet();
        //合并后的key（相当于剪枝）
        for (Integer x:keys) {
            if (counts.get(x)<=0) {
                continue;
            }
            aCase.addLast(x); //放到尾部
            counts.put(x, counts.getOrDefault(x, 0)-1);
            backtrack(nums, counts, aCase, res);
            aCase.removeLast(); //从尾部移除
            counts.put(x, counts.getOrDefault(x, 0)+1);
        }
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums.length<=0) {
            return new ArrayList<>();
        }

        Map<Integer, Integer> counts = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            counts.put(nums[i], counts.getOrDefault(nums[i], 0)+1);
        }
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> aCase = new ArrayDeque<>();
        backtrack(nums, counts, aCase, res);

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new LC47Permutations2().permuteUnique(new int[]{2,2,1,1}));
    }
}
